Proof of a conjecture of Davila and Kenter regarding a lower bound for the forcing number in terms of girth and minimum degree

摘要

In this note, we study a dynamic coloring of vertices in a simple graph $G$.In particular, one may color an initial set of vertices black, with all othervertices white. Then, at each discrete time step, a black vertex with exactlyone white neighbor will force its white neighbor to become black. The initialset of black vertices is called a zero forcing set if by iterating thisaforementioned process, all of the vertices in $G$ become black. The zeroforcing number of $G$ is the cardinality of a minimum zero forcing set in $G$,and is denoted by $Z(G)$. Davila and Kenter [Bounds for the zero forcing numberof a graph with large girth. Theory and Applications of Graphs, 2(2) (2015)]conjectured that the zero forcing number satisfies $Z(G)\geq(g-3)(\delta-2)+\delta$ where $g$ and $\delta$ denote the girth and the minimumdegree of the graph, respectively. This conjecture has been proven for graphswith girth $g \leq 10$. In this note, we prove it for all graphs with girth $g\geq 11$ and for all values of $\delta \geq 2$, thereby settling theconjecture.